Historically, computers were designed to perform repetitive calculations quickly and accurately. Today, advancements in the area of digital image processing, or more broadly digital signal processing, can be attributed to the increased ability of computers to perform repetitive calculations as quickly as possible.
A digital image is represented by a collection of pixels having different colors, or grayscale, intensity values. These images can be generated from any number of sources including scanners, medical equipment, or graphics programs. Alternatively, digital images can also be generated from analog images such as photographs. Typically, the collection of pixels are arranged in rows and columns. The color of a pixel at a particular x-y coordinate on a display screen or similar two-dimensional output device is represented by a groups of bits assigned a digital code associated with a color space. A Red, Green, and Blue (RGB) color space format is an additive color space in which various amounts of each of the RGB components are added together for a desired color.
Alternatively, color spaces YUV, YIQ, and YCbCr represent colors as color difference components. In the simplest gray-scale images, each pixel is represented by a luminance (or intensity value) using the Y component in each of these color spaces. Color images have additional groups of bits for the UV, IQ, and CbCr components in each of the respective color spaces which represent a chrominance component. Television, such as NTSC (National Television System Committee) or PAL (Phase Alternation Line), as well as digital image standards, such as MPEG (Moving Picture Expert Group), use the difference color space to represent pixels because they can be transmitted using less bandwidth, stored using less storage, and processed more quickly.
Modern digital image processing techniques involve manipulating these pixel values for image enhancement and image compression purposes. The goal of image enhancement usually involves processing groups of pixels and manipulating the bit values to achieve some special visual effect. Some image enhancements include image sharpening, image softening, and image blending.
In contrast, the goal of image compression is to represent an digital image, or any input signal, using a minimal amount of resources, while still being able to re-construct the original data or image. Depending on the complexity of each digital image, compression can sometimes reduce the size of data by 3 to 20 times of the original size. This is especially important for digital image processing, because of the vast amounts of data often involved. Recent advances in image processing have enabled people to download images quickly over the Internet and store the resulting data sets using relatively small storage requirements. For example, a landsat D satellite typically transmits an image size of 6100.times.6100 pixels, which, at 8 bits/pixel, translates to approximately 372 Megabytes of image data. Without compression, downloading such an image over the Internet or storing it on a storage device would not be feasible both economically or logistically.
Fortunately, it is not necessary to display all of the data for the reconstruction to be an adequate representation of the original. For this reason, "lossy" compression techniques are used which eliminate certain bits in the images which are unnecessary. This process of data compression can be divided into two parts. The first step removes redundant information in the image that is not be required for reconstruction. Generally, this is caused by inherently high degree of correlation between pixel values found in digital images. For example, standards such as MPEG.sup.1 isolates both temporal redundancies and spatial redundancies in digital video to eliminate unnecessary bits. Spatial redundancy occurs when objects in the image tend to have only slight variations in intensity or color across the area of a given frame image. Temporal redundancy occurs when a sequence of images tend to contain the same objects in approximately the same position in a sequence of frames. FNT 1. MPEG (Moving Pictures Expert Group) is a group of people that meet under ISO (International Standards Organization) to generate standards for digital video (temporal sequencing of images) and audio compression. MPEG is a nickname for the video/audio standards and the official name is ISO/IEC JTC 1 SC29 WG11 where IEC is International Electro-technical commission; JTC 1 is Joint Technical Committee 1; SC29 is Subcommittee 29; and WG11 is Work Group 11.
The second step in compression is to code the non-redundant data in such a way that the smallest possible number of bits are needed to represent the image. Variable length coding (VLC) techniques are used to code high frequency bit patterns in the image with shorter codes and low-frequency bit patterns in the image with longer codes. Typically, these coding techniques are based on variable length Huffman codes or arithmetic coding methods. Even though arithmetic coding methods can offer higher compression, licensing fees for the arithmetic coding methods result in most techniques adopting the Huffman coding methodologies. For example, MPEG encoding/decoding uses Huffman tables shown in FIG. 1 to code and decode bit patterns typically used to represent digital images. The code is variable length so that frequent bit patterns are represented using shorter codes and infrequent bit patterns are represented with longer codes. Overall, this technique tends to compress the images but makes decoding the information process intensive.
While image processing techniques, such as MPEG decoding/encoding, are performed using existing software libraries, generalized instructions are used in these libraries to drive the integer and floating point functional units. These generalized instructions and processors have difficulty performing pixel operations because they are performed sequentially. For example, to decode an MPEG video stream each group of pixels must be compared against a large number of variable length bit sequences. This requires the processor to perform many comparisons and branching operations. A sample of the variable length codes used in the Huffman decode tables for MPEG is shown in FIG. 1 for exemplary purposes only. Complete Huffman decode lookup tables typically include well over 100 different variable length entries. Large variable length lookup tables, such as Huffman decode lookup tables, represent a trade-off between compression and coding efficiency versus processing speed. At the processor level, conventional comparisons and decoding in these large lookup tables are executed on general purpose processors sequentially. This can make MPEG decoders for embedded systems and devices prohibitively expensive or, alternatively, unacceptably slow.
More sophisticated image processing techniques must be developed as the size of digital images increase. Ubiquitous computing, having one user operate many small embedded processors in devices both in business and home, also requires that image processing techniques become more efficient. These general purpose processors should execute instructions in parallel and take advantage of the parallelism inherent in image processing and data compression. Thus, there is a need to improve the techniques used to perform image processing routines used in image enhancement and compression. The present invention fulfills this need and other needs.